package test;

import java.util.Arrays;
import java.util.Scanner;

public class WangYi3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int[] n = new int[num];
        for (int i = 0; i < num; i++) {
            n[i] = scanner.nextInt();
        }
        for (int i = 0; i < num; i++) {
            System.out.println(getRes(n[i]) % 10007);
        }
    }

    private static int getRes(int n) {
        int[] dp = new int[n + 1];
        if (n <= 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < n + 1; i++) {
            for (int j = 1; j <= 3; j++) {
                dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
}
